class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        int ret=0;
        vector<int> mem(n);
        for(int i=0;i<n;++i)
            ret=max(ret,dfs(nums,i,mem));
        return ret;
    }

    int dfs(vector<int>& nums,int pos,vector<int>& mem)
    {
        if(mem[pos]!=0) return mem[pos];
        int n=nums.size();
        int ret=1;
        for(int i=pos+1;i<n;++i)
        {
            if(nums[i]>nums[pos])
            {
                ret=max(ret,dfs(nums,i,mem)+1);
            }
        }
        mem[pos]=ret;
        return mem[pos];
    }
};
